package com.cango.student.algorithm.sort;

/**
 * 快速排序
 * 时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
 * O(nlog2n) 	       O(n2)	      O(nlog2n)	    O(nlog2n)	不稳定	较复杂
 *
 * 选取最优基准值，然后两个指针，一个指向最左大于基准的值，另一个是全遍历指针，最后交换基准和最左大于基准。
 */
public class Quicksort2 {

    static int[] a = {40, 9, 20, 4, 30, 1, 54, 6, 8, 99};
//    static int[] a = {6, 11, 3, 9, 8};

    public static void quicksort(int left, int right) {
        if (left > right)
            return;

        // 基准值
        ChoosePivotkey(a,left,right);
        int temp = a[right];
        // 盯住最左的大于基准值
        int i = left;
        // 前进值
        int j = left;

        while (j != right) {
            // 前进值小于基准值，盯住最左的大于基准值
            if (a[j] < temp) {
                Swap(a, i, j);
                i++;
            }
            j++;
        }
        a[right] = a[i];
        a[i] = temp;

        quicksort(left, i - 1);
        quicksort(i + 1, right);
    }

    public static void Swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    //三数取中 选择枢轴    将枢轴值调至第一个位置
    public static void ChoosePivotkey(int[] arr, int low, int high) {
        int mid = (low + high) / 2;

        // 左右比较，左边为大
        if (arr[low] < arr[high]) {
            Swap(arr, low, high);
        }
        // 中左比较，左边为大
        if (arr[mid] > arr[low]) {
            Swap(arr, mid, low);
        }

        // 中右比较，右边为中间值
        if (arr[mid] > arr[high]) {
            Swap(arr, mid, high);
        }
    }

    public static void main(String[] args) {

        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");

        quicksort(0, a.length - 1); //快速排序调用
        System.out.println();
        //输出排序后的结果
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
    }
}
